package bintree;


import java.util.Deque;
import java.util.LinkedList;

class  TreeNode<E> {
    public TreeNode(E val) {
        this.val = val;
    }

    E val;
    TreeNode<E> left;
    TreeNode<E> right;
}
public class MyBinTree<E> {

    public TreeNode<Character> root;

    public void build(){
        TreeNode<Character> node0 = new TreeNode<>('A');
        TreeNode<Character> node1 = new TreeNode<>('B');
        TreeNode<Character> node2 = new TreeNode<>('C');
        TreeNode<Character> node3 = new TreeNode<>('D');
        TreeNode<Character> node4 = new TreeNode<>('E');
        TreeNode<Character> node5 = new TreeNode<>('F');
        TreeNode<Character> node6 = new TreeNode<>('G');
        TreeNode<Character> node7 = new TreeNode<>('H');
        node0.left = node1;
        node0.right = node2;
        node1.left = node3;
        node1.right = node4;
        node4.left = node6;
        node6.right = node7;
        node2.right = node5;
        root = node0;
    }

    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }

        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        preOrder(root.left);
        System.out.print(root.val+" ");
        preOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val+" ");
    }
//节点个数
    public int getNodes(TreeNode root){
        if (root == null){
            return 0;
        }

        return 1+getNodes(root.left)+getNodes(root.right);
        // return root == null?0:1+getNodes(root.left)+getNodes(root.right);
    }
//使用层序遍历统计一颗二叉树的结点个数
public int gerNodesNonRecursion(TreeNode root){
        if (root==null){
            return 0;
        }
        int size = 0;
    Deque<TreeNode<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        TreeNode cur = queue.poll();
        size++;
        if (cur.left!=null){
            queue.offer(cur.left);
        }
        if (cur.right!=null){
            queue.offer(cur.right);
        }
    }
    return size;
}


//叶子结点
    public int getLeafNodes(TreeNode root){
        if (root==null){
            return 0;
        }
        if ((root.left=root.right) == null){
            return 1;
        }
        return getNodes(root.left)+getNodes(root.right);
    }

//第K层二叉树节点的个数<=height
    public int getKLecelNodes(TreeNode root,int k){
        //1.边界条件
        if (root == null || k<=0){
            return 0;
        }
        if (k==1){
            return 1;
        }
        //求以root
        return getKLecelNodes(root.left,k-1)+getKLecelNodes(root.right,k-1);
    }

    //树的高度
    public int height(TreeNode root){
        if (root == null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));
    }
    //包含指定值val
    public boolean contains(TreeNode<E> root,E val){
       if (root == null){
           return false;
       }
       if (root.val.equals(val)){
           return true;
       }
       return contains(root.left,val)||contains(root.right,val);
    }
    //借助队列，实现了二叉树的层序遍历
    public void levelOrder(TreeNode<E> root){
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode<E> node =queue.poll();
                System.out.println(node.val+" ");
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
    }
}
